﻿public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val=0, ListNode next=null) 
    { 
        this.val = val;
        this.next = next;
    }
}
public class Solution {
    public ListNode RemoveNthFromEnd(ListNode head, int n)
    {
        if (n <= 0)
        {
            return head;
        }

        ListNode H = new ListNode(0, head);
        // 定义快慢指针
        ListNode fast = H, slow = H;
        for (int i = 0; i < n + 1; i++)
        {
            if (fast is null)
            {
                return head;
            }
            fast = fast.next;
        }

        while (fast is not null)
        {
            fast = fast.next;
            slow = slow.next;
        }

        slow.next = slow.next.next;
        return H.next;
    }

    public static void Main(string[] args)
    {
        int[] head = [1, 2, 3, 4, 5];
        int n = 2;
        
        // 构建链表
        ListNode headNode = new ListNode(head[0]);
        ListNode pre = headNode;
        foreach (int h in head[1..])
        {
            ListNode l = new ListNode(h);
            pre.next = l;
            pre = pre.next;
        }
        
        // 移除倒数第n个元素
        Solution solution = new Solution();
        headNode = solution.RemoveNthFromEnd(headNode, n);
        pre = headNode;
        while (pre is not null)
        {
            Console.Write($"{pre.val} ");
            pre = pre.next;
        }
    }
}